/**
 * @file   1052.cpp
 * @author Shuang Hu <hsmath@ubuntu>
 * @date   Mon Apr 12 02:29:19 2021
 * 
 * @brief  PAT advanced 1052:Linked list sorting
 * 
 * 
 */

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
using namespace std;
class Node{
private:
    int myaddress;
    int data;
    int nextaddress;
public:
    Node(){
    }
    void setinfo(int add1,int data,int add2){
	this->data=data;
	myaddress=add1;
	nextaddress=add2;
    }
    int getdata(){
	return data;
    }
    void setnext(int add){
	nextaddress=add;
    }
    int getadd(){
	return myaddress;
    }
    int getnext(){
	return nextaddress;
    }
};
class LinkedList{
private:
    int nodenum;
    int rootaddress;
    vector<Node> List;
    vector<Node> TrueList;
    map<int,int> Address;
    map<int,int> nodes;
public:
    LinkedList(int num,int add){
	nodenum=num;
	rootaddress=add;
    }
    void Build();//Build a linked list
    void Sort();//Sort the linked list
    void Print();//Print the linked list
};
void LinkedList::Build(){
    for(int i=0;i<nodenum;i++){
	Node N;
	int add1,data,add2;
	cin>>add1>>data>>add2;
	N.setinfo(add1,data,add2);
	Address[add1]=add2;//add1->add2
	nodes[add1]=i;//add1 means i-th node
	List.push_back(N);
    }
    int add=rootaddress;
    nodenum=0;
    while(add!=-1){
	if(nodes.count(add)==0){
	    break;
	}
	TrueList.push_back(List[nodes[add]]);
	add=Address[add];
	nodenum++;
    }
}
bool cmp(Node &N1,Node &N2){
    if(N1.getdata()<=N2.getdata()){
	return true;
    }else{
	return false;
    }
}
void LinkedList::Sort(){
    sort(TrueList.begin(),TrueList.end(),cmp);
    if(nodenum){
    for(int i=0;i<TrueList.size()-1;i++){
	TrueList[i].setnext(TrueList[i+1].getadd());
    }
    TrueList[TrueList.size()-1].setnext(-1);
    rootaddress=TrueList[0].getadd();
    }
}
void output(int add){
    if(add>=10000){
	cout<<add;
    }else if(add>=1000){
	cout<<"0"<<add;
    }else if(add>=100){
	cout<<"00"<<add;
    }else if(add>=10){
	cout<<"000"<<add;
    }else if(add>=0){
	cout<<"0000"<<add;
    }else{
	cout<<add;
    }
}
void LinkedList::Print(){
    if(nodenum==0){
	cout<<"0 -1"<<endl;
	return;
    }
    cout<<nodenum<<" ";
    output(rootaddress);
    cout<<endl;
    for(int i=0;i<TrueList.size();i++){
	output(TrueList[i].getadd());
	cout<<" "<<TrueList[i].getdata()<<" ";
	output(TrueList[i].getnext());
	cout<<endl;
    }
}
int main(){
    int nodenum,root;
    cin>>nodenum>>root;
    LinkedList L(nodenum,root);
    L.Build();
    L.Sort();
    L.Print();
}
